#include "pch.h"
#include <iostream>
#include <map>

using namespace std;

class Solution {
public:
	int climbStairs(int n) {
		map<int,int> m;
		for (int i = 1;i <= n;i++)
		{
			cout << i << endl;
			if (i == 1)
			{
				m[1] = 1;
				continue;
			}

			if (i == 2)
			{
				m[2] = 2;
				continue;
			}
			//if(!m.count(n))
			m[i] = m[i - 1] + m[i - 2];
		}
		return m[n];
	}
};

int main()
{
	Solution s;
	int num = 44;
	int res = s.climbStairs(num);
	cout << res << endl;

	return 0;
}